\input{euler.tex}

\begin{document}

\problem[169]{Express A Number As Sum of Powers of 2}

Define $f(0)=1$ and $f(n)$ to be the number of different ways $n$ can be expressed as a sum of integer powers of 2 using each power no more than twice.
 
For example, $f(10)=5$ since there are five different ways to express 10:
\begin{align} 
10 &= 1 + 1 + 8 \notag \\
10 &= 1 + 1 + 4 + 4 \notag \\
10 &= 1 + 1 + 2 + 2 + 4 \notag \\
10 &= 2 + 4 + 4 \notag \\
10 &= 2 + 8 \notag 
\end{align}

Find $f(10^{25})$.

\solution

To express a \emph{positive} integer $n$ as the sum of powers of 2, i.e.
\[
n = c_k \times 2^k + c_{k-1} \times 2^{k-1} + \cdots + c_0 \times 2^0
\]
where $0 \le c_i \le 2$, start with the smallest power, $2^0 = 1$. If $n$ is odd, then $c_0 = 1$ because all the rest terms are even and their sum is even. If $n$ is even, then $c_0 = 0$ or 2.

Once we fix the lowest power, we can work on the higher powers. Rewriting
\[
\frac{n - c_0}{2} = c_k \times 2^{k-1} + \cdots + c_1 \times 2^0 ,
\]
it can be seen that the number of ways to construct the remaining sum is exactly $f\left(\frac{n-c_0}{2}\right)$.

Thus we find the following recurrence relation:
\begin{equation}
f(n) = 
\begin{cases} 
f\left(\frac{n-1}{2}\right), & \mbox{if } n\mbox{ is odd;} \\
f\left(\frac{n-0}{2}\right) + f\left(\frac{n-2}{2}\right), & \mbox{if } n\mbox{ is even.} 
\end{cases} \label{eq:169.1}
\end{equation}
The boundary condition is $f(0) = f(1) = 1$.

To simplify equation \eqref{eq:169.1}, define
\[
g(a, b; k) = a f(k)+b f(k-1), 
\]
and note that when $k$ is odd, 
\begin{align}
g(a,b;k) &= a f\left(\frac{k-1}{2}\right) + b\left[ f\left(\frac{k-1}{2}\right) + f\left(\frac{k-1}{2}-1\right)\right] \notag \\
&= g\left(a+b, b; (k-1)/2 \right) , \notag
\end{align}
and when $k$ is even,
\begin{align}
g(a,b;k) &= a \left[ f\left(\frac{k}{2}\right) + f\left(\frac{k}{2}-1\right)\right] + b\left(\frac{(k-1)-1}{2}\right) \notag \\
&= g(a,a+b; k/2) . \notag
\end{align}
The boundary condition is $g(a, b; 1) = a+b$. With these recurrence relations, $g(a, b; k)$ can be computed in $\log_2 k$ steps.

Finally, if $n = 2^k d$ where $d$ is odd, then
\[
f(n) = f(2^k d) = g(1,1; 2^{k-1} d ) = \cdots = g(1,k; 2^0 d) .
\]
This handy relation can be used to find the answer to this problem.

\complexity

Time complexity: $\BigO(\log_2 n)$.

Space complexity: $\BigO(\log_2 n)$.

\answer

178653872807



\end{document} 